0659. 分割数组为连续子序列【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心

1. 📝 题目描述

• leetcode

给你一个按 非递减顺序 排列的整数数组 nums。

请你判断是否能在将 nums 分割成 一个或多个子序列 的同时满足下述 两个 条件：

• 每个子序列都是一个 连续递增序列（即，每个整数 恰好 比前一个整数大 1 ）。
• 所有子序列的长度 至少 为 3。

如果可以分割 nums 并满足上述条件，则返回 true ；否则，返回 false。

---

示例 1：

输入：nums = [1,2,3,3,4,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5

示例 2：

输入：nums = [1,2,3,3,4,4,5,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5

示例 3：

输入：nums = [1,2,3,4,4,5]
输出：false
解释：无法将 nums 分割成长度至少为 3 的连续递增子序列。

---

提示：

• 1 <= nums.length <= 10^4
• -1000 <= nums[i] <= 1000
• nums 按非递减顺序排列

2. 🎯 s.1 - 贪心

c

// 简化实现：使用偏移数组代替哈希表
bool isPossible(int* nums, int numsSize) {
    if (numsSize < 3) return false;
    int mn = nums[0], mx = nums[numsSize - 1];
    int range = mx - mn + 1;
    int* freq = (int*)calloc(range, sizeof(int));
    int* tail = (int*)calloc(range + 3, sizeof(int));
    for (int i = 0; i < numsSize; i++) freq[nums[i] - mn]++;
    for (int i = 0; i < numsSize; i++) {
        int n = nums[i] - mn;
        if (freq[n] == 0) continue;
        if (tail[n] > 0) {
            freq[n]--; tail[n]--; tail[n + 1]++;
        } else if (n + 2 < range && freq[n + 1] > 0 && freq[n + 2] > 0) {
            freq[n]--; freq[n + 1]--; freq[n + 2]--; tail[n + 3]++;
        } else {
            free(freq); free(tail); return false;
        }
    }
    free(freq); free(tail);
    return true;
}

js

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isPossible = function (nums) {
  const freq = new Map()
  const tail = new Map()
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1)
  for (const n of nums) {
    if (freq.get(n) === 0) continue
    if ((tail.get(n) || 0) > 0) {
      freq.set(n, freq.get(n) - 1)
      tail.set(n, tail.get(n) - 1)
      tail.set(n + 1, (tail.get(n + 1) || 0) + 1)
    } else if ((freq.get(n + 1) || 0) > 0 && (freq.get(n + 2) || 0) > 0) {
      freq.set(n, freq.get(n) - 1)
      freq.set(n + 1, freq.get(n + 1) - 1)
      freq.set(n + 2, freq.get(n + 2) - 1)
      tail.set(n + 3, (tail.get(n + 3) || 0) + 1)
    } else {
      return false
    }
  }
  return true
}

py

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        freq = Counter(nums)
        tail = Counter()
        for n in nums:
            if freq[n] == 0:
                continue
            if tail[n] > 0:
                freq[n] -= 1
                tail[n] -= 1
                tail[n + 1] += 1
            elif freq[n + 1] > 0 and freq[n + 2] > 0:
                freq[n] -= 1
                freq[n + 1] -= 1
                freq[n + 2] -= 1
                tail[n + 3] += 1
            else:
                return False
        return True

• 时间复杂度：$O(n)$，其中 n 是数组长度
• 空间复杂度：$O(n)$

算法思路：

• 维护频次表 freq 和尾部表 tail（记录以某数结尾的序列数）
• 优先将当前数接到已有序列尾部，否则新建长度为 3 的序列
• 两者都无法满足则返回 false